#include <iostream>
#include <vector>
#include <stack>
#include <string>
#include <list>
#include <queue>
using namespace std;


struct ListNode {
    int val;
    struct ListNode* next;
    ListNode(int x) : val(x), next(nullptr)
    {}
};

//class Solution {
//public:
//    ListNode* mergeKLists(vector<ListNode*>& lists) {
//        // write code here
//        int n = lists.size();
//        if (n == 0)
//        {
//            return nullptr;
//        }
//        ListNode* phead = nullptr;
//        ListNode* root = nullptr;
//        while (1)
//        {
//            int my_min = 1001;
//            int min_addr = 0;
//            ListNode* cur = lists[min_addr];
//            while (cur == nullptr && min_addr < n - 1)
//            {
//                cur = lists[++min_addr];
//            }
//            for (int i = min_addr; i < n; i++)
//            {
//                if (!lists[i])
//                {
//                    continue;
//                }
//                if (my_min > lists[i]->val)
//                {
//                    my_min = lists[i]->val;
//                    min_addr = i;
//                }
//            }
//            if (lists[min_addr] == nullptr)
//            {
//                break;
//            }
//            if (phead == nullptr)
//            {
//                root = phead = lists[min_addr];
//                lists[min_addr] = lists[min_addr]->next;
//            }
//            else
//            {
//                root->next = lists[min_addr];
//                root = root->next;
//                lists[min_addr] = lists[min_addr]->next;
//            }
//        }
//        if(root)
//        {
//            root->next = nullptr;
//        }
//        return phead;
//    }
//};


class Solution {
public:
    void _HeapSort(vector<ListNode*>& list, int i, int n)
    {
        int parent = i;
        int child = parent * 2 + 1;
        while (child < n)
        {
            if (child + 1 < n && list[child]->val < list[child + 1]->val)
            {
                child++;
            }
            if (list[child]->val > list[parent]->val)
            {
                swap(list[child], list[parent]);
                parent = child;
                child = parent * 2 + 1;
            }
            else
            {
                break;
            }
        }
    }

    void Heapsort(vector<ListNode*>& list)
    {
        int n = list.size();
        for (int i = (n - 1 - 1) / 2; i >= 0; i--)
        {
            _HeapSort(list, i, n);
        }
        int end = n - 1;
        while (end)
        {
            swap(list[0], list[end]);
            _HeapSort(list, 0, end);
            end--;
        }
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        // write code here
        int n = lists.size();
        if (n == 0)
        {
            return nullptr;
        }
        vector<ListNode*> list;
        for (int i = 0; i < n; i++)
        {
            ListNode* cur = lists[i];
            while (cur)
            {
                list.push_back(cur);
                cur = cur->next;
            }
        }
        if (list.size() == 0)
        {
            return nullptr;
        }
        Heapsort(list);
        ListNode* phead = nullptr;
        n = list.size();
        phead = list[0];
        ListNode* cur = phead;
        for (int i = 1; i < n; i++)
        {
            cur->next = list[i];
            cur = cur->next;
        }
        cur->next = nullptr;
        return phead;
    }
};

int main()
{
    vector<ListNode*> list;
    //ListNode* node1 = new ListNode(-5);
    //ListNode* node2 = new ListNode(-9);
    //node2->next = new ListNode(-8);
    //ListNode* cur = node2->next;
    //cur->next = new ListNode(-7);
    //cur = cur->next;
    //cur->next = new ListNode(1);
    //cur = cur->next;
    //cur->next = new ListNode(1);
    //cur = cur->next;
    //cur->next = new ListNode(1);
    //cur = cur->next;
    //cur->next = new ListNode(3);
    //ListNode* node3 = new ListNode(-10);
    //node3->next = new ListNode(-7);
    //cur = node3->next;
    //cur->next = new ListNode(-6);
    //cur = cur->next;
    //cur->next = new ListNode(-6);
    //cur = cur->next;
    //cur->next = new ListNode(-6);
    //cur = cur->next;
    //cur->next = new ListNode(0);
    //cur = cur->next;
    //cur->next = new ListNode(1);
    //cur = cur->next;
    //cur->next = new ListNode(3);
    //cur = cur->next;
    //cur->next = new ListNode(3);
    //cur = cur->next;
    //ListNode* node4 = new ListNode(-10);
    //node4->next = new ListNode(-8);
    //cur = node4->next;
    //cur->next = new ListNode(-7);
    //cur = cur->next;
    //cur->next = new ListNode(-2);
    //cur = cur->next;
    //cur->next = new ListNode(3);
    //cur = cur->next;
    //cur->next = new ListNode(3);
    //cur = cur->next;
    //ListNode* node5 = new ListNode(-1);
    //node5->next = new ListNode(4);
    //ListNode* node6 = new ListNode(-5);
    //node6->next = new ListNode(-4);
    //node6->next->next = new ListNode(-1);
    //list.push_back(node1);
    //list.push_back(node2);
    //list.push_back(node3);
    //list.push_back(node4);
    //list.push_back(node5);
    //list.push_back(node6);
    list.push_back(nullptr);
    Solution s;
    s.mergeKLists(list);
    return 0;
}

class Solution {
public:
    bool hasCycle(ListNode* head) {
        if (head == nullptr)
        {
            return false;
        }
        ListNode* cur = head;
        ListNode* prev = head;
        while (cur && prev)
        {
            prev = prev->next;
            cur = cur->next;
            if (cur == nullptr)
            {
                return false;
            }
            cur = cur->next;
            if (cur == prev)
            {
                return true;
            }
        }
        return false;
    }
};

class Solution {
public:
    ListNode* sortInList(ListNode* head) {
        // write code here
        if (head == nullptr)
        {
            return nullptr;
        }
        ListNode* phead = nullptr;
        ListNode* root = nullptr;
        while (head)
        {
            ListNode* min_node = head;
            ListNode* min_prev = head;
            ListNode* cur = head;
            ListNode* prev = nullptr;
            while (cur)
            {
                if (cur->val < min_node->val)
                {
                    min_node = cur;
                    min_prev = prev;
                }
                prev = cur;
                cur = cur->next;
            }
            if (head == min_node)
            {
                head = head->next;
            }
            if (phead == nullptr)
            {
                min_prev->next = min_node->next;
                root = phead = min_node;
            }
            else
            {
                min_prev->next = min_node->next;
                root->next = min_node;
                root = root->next;
            }
        }
        return phead;
    }
};


class Solution {
public:
    struct my_Sort
    {
        bool operator()(ListNode* l1, ListNode* l2)
        {
            return l1->val < l2->val;
        }
    };

    ListNode* sortInList(ListNode* head) {
        // write code here
        vector<ListNode*> lists;
        ListNode* cur = head;
        while (cur)
        {
            lists.push_back(cur);
            cur = cur->next;
        }
        sort(lists.begin(), lists.end(), my_Sort());
        ListNode* phead;
        phead = lists[0];
        ListNode* root = phead;
        for (auto l : lists)
        {
            root->next = l;
            root = root->next;
        }
        root->next = nullptr;
        return phead;
    }
};